/**
 * 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * [
 *   [1,1,1],
 *   [1,0,1],
 *   [1,1,1]
 * ]
 * 输出:
 * [
 *   [1,0,1],
 *   [0,0,0],
 *   [1,0,1]
 * ]
 * 一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个常数空间的解决方案吗？
 */
class Solution {

    public static void main(String[] args) {
        int[][] matrix = new int[3][4];
        int[] a1 = new int[]{1, 2, 3, 4};
        int[] a2 = new int[]{5, 0, 7, 8};
        int[] a3 = new int[]{9, 10, 11, 12};
        matrix[0] = a1;
        matrix[1] = a2;
        matrix[2] = a3;
        setZeroes(matrix);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + ",");
            }
            System.out.println("");
        }
    }

    public static void setZeroes(int[][] matrix) {
        int height = matrix.length;
        int length = matrix[0].length;
        // 找到第一个0，把第一个0所在列当做是有没有0的判断
        int i = 0, j = 0;
        find:
        for (; i < height; i++) {
            for (j = 0; j < length; j++) {
                if (matrix[i][j] == 0) {
                    break find;
                }
            }
        }
        if (i != height && j != length) {
            for (int k = i + 1; k < height; k++) {
                for (int l = 0; l < length; l++) {
                    if (matrix[k][l] == 0) {
                        matrix[k][j] = 0;
                        matrix[i][l] = 0;
                    }
                }
            }
            for (int k = 0; k < height; k++) {
                if (matrix[k][j] == 0 && k != i) {
                    for (int l = 0; l < length; l++) {
                        matrix[k][l] = 0;
                    }
                }
            }
            for (int k = 0; k < length; k++) {
                if (matrix[i][k] == 0) {
                    for (int l = 0; l < height; l++) {
                        matrix[l][k] = 0;
                    }
                }
            }
            for (int k = 0; k < length; k++) {
                matrix[i][k] = 0;
            }
        }
    }
}